public class Sort {
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    public static void ShellSort(int[] array){
        int gap = array.length;
        while (gap>1){
            gap/=2;
            Shell(array,gap);
        }
    }
    public static void Shell( int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0 ; j-=gap) {
                if (array[j] > tmp){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp= array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left<right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right ; i++) {
                if (array[i] < array[minIndex]){
                    minIndex = i;
                }
                if (array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            //最大值刚好在最小值的位置，已经交换到了minIndex
            if (maxIndex == left){
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    public static void heapSort(int[] array){
        creatBigHeap(array);
        int end = array.length-1;
        while (end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    public static void creatBigHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
            siftDown(array,parent,array.length);
        }
    }
    public static void siftDown(int[] array,int parent,int end){
        int child = 2*parent +1;
        while (child<end){
            if (child+1 < end&&array[child] < array[child+1]){
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent +1;
            }else {
                break;
            }
        }
    }

    public static void BubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (!flg){
                return;
            }
        }
    }

    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if (start>=end){
            //左边是一个结点或者一个都没有
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static int partitionHoare(int[] array,int left,int right){
        int key = array[left];
        int i = left;
        while (left < right){
            while (left < right && array[right] >= key){
                right--;
            }
            while (left < right && array[left] <= key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,right,i);
        return left;
    }


    public static int partition(int[] array,int left,int right){
        int key = array[left];
        while (left < right){
            while (left < right && array[right] >= key){
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= key){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }

    public  void Extest(){
        int i = 1;
        if (i == 1){
            throw new Ex("数据不合理");
        }else {
            return;
        }
    }

}
